정렬 알고리즘 (비교)

r5 ➤ r6
10====의사 코드(간이화)====
11다음은 선택 정렬의 의미를 간단히이화하여 서술한 코드이다.
19====의사 코드====
20다음은 의사코드 1에서 큰 수를 찾고, 두 수를 교환하는 과정을 엄밀하게 서술한 코드이다.
39====의사 코드 (간이화)====
40다음은 버블 정렬의 의미를 간단히이화하여 서술한 코드이다.
49====의사 코드====
50다음은 이미 정렬이 완료된 상태이면 작업을 종료한하여 효율을 높인 코드이다.
51
66====의사 코드 (간이화)====
67다음은 삽입 정렬의 의미를 간단히이화하여 서술한 코드이다.
74====의사 코드 (재귀)====다음은 재귀를 이용한 코드이다.
82====의사 코드 ====
83다음은 적합한 자리를 찾는 로직을 풀어 서술한 코드이다.
95===병합 정렬(Merge Sort)===
96===퀵 정렬(Quick Sort)===
97===힙 정렬(Heap Sort)===
98===셸 정렬(Shell Sort)===전체 리스트를 절반으로 계속 나누어 각 부분을 정렬한 후, 다시 병합하는 분할 정복 기반의 정렬 알고리즘이다. 합병 정렬이라고도 한다.
99===병합 정렬(Merge Sort)===
100====의사 코드====
101다음은 병합 정렬의 의미를 간단히 서술한 코드이다.
102
103{{{#!syntax java
104mergeSort(A[], p, r):
105 if (p < r)
106 q ← ⌊(p+r)/2⌋
107 mergeSort(A, p, q)
108 mergeSort(A, q+1, r)
109 merge(A, p, q, r)
110
111merge(A[], p, q, r):
112 정렬된 두 배열 A[p…q]와 A[q+1…r]을 합쳐
113 정렬된 하나의 배열 A[p…r]을 만든다.
114}}}
115다음은 병합 함수(merge)를 풀어 서술한 코드이다.
116
117{{{#!syntax java
118merge(A[], p, q, r):
119 i ← p; j ← q+1; t ← 0
120 while (i ≤ j q and j ≤ r)
121 if (A[i] ≤ A[j]) tmp[t++] ← A[i++]
122 else tmp[t++] ← A[j++]
123 while (i ≤ q)
124 tmp[t++] ← A[i++]
125 while (j ≤ r)
126 tmp[t++] ← A[j++]
127 i ← p; t ← 0
128 while (i ≤ r)
129 A[i++] ← tmp[t++]
130}}}
131====분석====
132병합 정렬의 수행 시간은 모든 경우에 [math(\Theta(n\log n))]이다. 이 알고리즘은 비교 횟수를 기준으로 수행 시간을 분석해도 되지만 비교 횟수보다 더 잦은 작업이 있다. 바로 원소를 옮기는 작업으로, A[]와 tmp[]를 번갈아 옮기기 때문에 어떤 경우든 [math(2n)]번의 이동이 일어난다. 비교횟수를 기준으로 분석하면 이 때는 [math(2n)] 대신 [math(n/2)] ~ [math(n-1)]이 된다. 점근적 분석 결과는 원소 이동 횟수와 비교 횟수가 동일하지만 시간을 지배하는 작업을 하나 정한다면 이동 횟수가 더 정확한 기준이 된다. 크기가 m인 배열을 병합 정렬로 처리하는 시간을 T(n)이라고 하면 다음과 같다.
133[math({\rm{T}}(n)=\begin{cases}\displaystyle 1 & \quad (n = 1) \\\displaystyle 2T(\frac{n}{2})+2n &\quad (n > 1) \end{cases} )]
134
135[[시간 복잡도#s-3.3|마스터 정리]]을 사용하면 [math(\Theta(n\log n))]이라는 것을 알 수 있다.
136===퀵 정렬(Quick Sort)===
137분할 정복 기법을 사용하여 기준값(피벗)을 중심으로 데이터를 작은 값과 큰 값으로 나누고, 이 과정을 재귀적으로 반복하여 매우 빠르게 데이터를 정렬하는 알고리즘이다.
138===힙 정렬(Heap Sort)===
139힙 자료구조를 이용해 데이터를 정렬하는 알고리즘으로, 배열을 최대 힙(또는 최소 힙)으로 만든 뒤, 루트(가장 크거나 작은 값)를 배열의 마지막 요소와 교환하고 힙 크기를 줄이는 과정을 반복하는 알고리즘이다. 본 문서에서는 가장 큰 원소 맨 위의 노드에 삽입하는 것을 기준으로 서술한다.
140===셸 정렬(Shell Sort)===
141삽입 정렬의 단점을 보완한 알고리즘으로, 처음에는 큰 간격으로 데이터를 나눠 부분 정렬을 하고, 간격을 점점 줄여가며 최종적으로는 전체 데이터를 효율적으로 정렬하는 알고리즘이다.